package editor.cn;

//Given a string s, return the longest palindromic substring in s. 
//
// 
// Example 1: 
//
// 
//Input: s = "babad"
//Output: "bab"
//Note: "aba" is also a valid answer.
// 
//
// Example 2: 
//
// 
//Input: s = "cbbd"
//Output: "bb"
// 
//
// Example 3: 
//
// 
//Input: s = "a"
//Output: "a"
// 
//
// Example 4: 
//
// 
//Input: s = "ac"
//Output: "a"
// 
//
// 
// Constraints: 
//
// 
// 1 <= s.length <= 1000 
// s consist of only digits and English letters (lower-case and/or upper-case), 
//
// 
// Related Topics 字符串 动态规划 
// 👍 2950 👎 0

public class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        System.out.println(solution.longestPalindrome("cbbd"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            char[] chars = s.toCharArray();
            int num = 0;
            int left = 0;
            for (int i = 0; i < chars.length; i++) {
                int r = chars.length - 1;
                int l = i;
                while (l <= r) {
                    if (chars[r] == chars[l]) {
                        int head = l;
                        int tail = r;
                        int count = 0;
                        while (head <= tail) {
                            if (chars[head] != chars[tail]) {
                                break;
                            }
                            if (tail - head == 1 && count + 2 > num) {
                                num = count + 2;
                                left = i;
                                break;
                            } else if (tail ==head && count + 1 > num) {
                                num = count + 1;
                                left = i;
                                break;
                            } else {
                                count += 2;
                                head++;
                                tail--;
                            }
                        }
                    }
                    r--;

                }
            }
            StringBuffer result = new StringBuffer();
            for (int i = left; i < left + num; i++) {
                result.append(chars[i]);
            }
            return String.valueOf(result);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}